The Pointwise Mutual Information (PMI) boundary detection algorithm can achieve the boundary of each image accurately, however the efficiency is restricted by the redundancy and randomness of sampling process. In order to overcome the disadvantage, a new method based on the middle structure information provided by super-pixel segmentation was proposed. Firstly, the image was divided into approximately the same super-pixels in the pre-processing. Secondly, the sampling points were located in adjacent different super-pixels which made the sample selection be more ordered, and the image information could still be extracted effectively and completely even though the total number of sampling points was reduced sharply. The comparison experiment of the proposed algorithm and the original PMI boundary detection algorithm was carried out on the Berkeley Segmentation Data Set (BSDS). The results show that the proposed algorithm achieves 0.7917 AP (Average Precision) under PR (Precision/Recall) curve with 3500 sample points, while the original algorithm needs 6000 pairs. It confirms that the proposed algorithm can guarantee the detection accuracy with reducing sample points, which improves the real-time performance effectively.